/*
Problem:    4 Sum
Difficulty: medium
Source:     http://www.leetcode.com/onlinejudge
Notes:
Given an array S of n integers, are there elements a, b, c, and d in S such that
a + b + c + d = target? Find all unique quadruplets in the array which gives the sum
of target.
Elements in a quadruplet (a,b,c,d) must be in non-descending order. (ie, a ≤ b ≤ c ≤ d)
The solution set must not contain duplicate quadruplets.
For example, given array S = {1 0 -1 0 -2 2}, and target = 0.

A solution set is:
(-1,  0, 0, 1)
(-2, -1, 1, 2)
(-2,  0, 0, 2)
*/
#include <iostream>
#include <vector>
#include <utility>
#include <algorithm>
#include <set>
#include <iterator>
#include <functional>

using namespace std;

class Solution {

public:
	vector<vector<int> > fourSum(vector<int> &num, int target) {
		vector<vector<int> > result;
		if (num.size() < 4)
			return result;

		vector<pair<int, pair<int, int> > > two_sum;
		for (int i = 0; i < num.size() - 1; i++) {
			for (int j = i + 1; j <num.size(); j++)
				two_sum.push_back(make_pair(num[i] + num[j], make_pair(i, j)));
		}
		sort(two_sum.begin(), two_sum.end(), compare);
		vector<int> tuple(4);
		set<vector<int> > result_set;
		for (int i = 0; i < two_sum.size() - 1; i++) {
			int v = target - two_sum[i].first;
			vector<pair<int, pair<int, int> > >::iterator find = 
				lower_bound(two_sum.begin(), two_sum.end(), make_pair(v, make_pair(0, 0)), compare);
			while (find->first == v && find != two_sum.end()) {
				int index_1 = find->second.first;
				int index_2 = find->second.second;
				int index_3 = two_sum[i].second.first;
				int index_4 = two_sum[i].second.second;

				if (index_1 != index_3 && index_1 != index_4 && index_2 != index_3 && index_2 != index_4) {
					tuple[0] = num[index_1];
					tuple[1] = num[index_2];
					tuple[2] = num[index_3];
					tuple[3] = num[index_4];
					sort(tuple.begin(), tuple.end());
					result_set.insert(tuple);
				}
				++find;
			}
		}
		copy(result_set.begin(), result_set.end(), back_inserter(result));
		
		return result;
	}
private:
	static bool compare(const pair<int, pair<int, int> >& lhs, const pair<int, pair<int, int> >& rhs) {
		return (lhs.first < rhs.first);
	}
};

int main(int argc, char* argv[])
{
	Solution s;
	int a[] = {1, 0, -1, 0, -2, 2, 0, 0, 0};
	vector<int> num;
	int target = 0;
	for (int i = 0; i < 9; i++)
		num.push_back(a[i]);
	vector<vector<int> > result = s.fourSum(num, target);
	for (int i = 0; i < result.size(); i++)
		cout << result[i][0] << " " << result[i][1] << " " << result[i][2] << " " << result[i][3] << " " << endl;
	return 0;
}